googologywikiaorg_ja-20200214-history
ユーザー:Kyodaisuu/砂場
自分専用の砂場です。本体にアップする前の下書き等に使います。 Sandbox / 砂場@ヘルプ / 利用者:Kyodaisuu/注目のウィキアン ---- �������� A program which calculates \(f_{\epsilon_0+1}(10)\) was posted at googology thread of Japanese BBS 2ch.net.BASIC program of \(\epsilon_0\) level Aycabta translated this program to C and Ruby.Translation of the program dim A(Infinity):B=9 for C=0 to 9 for D=0 to B A(D)=D next for E=B to 0 step -1 B=B*B for F=0 to E if A(E-F) Linear array and ordinal Linear array A is stored in parameters A(0) to A(E). For example, when E=3, A(0)=0, A(1)=1, A(2)=2, A(3)=3, we express this linear array as (0,1,2,3). Ordinal \(\alpha < \epsilon_0\) is expressed with linear array as follows. # Draw Kirby-Paris hydra of the ordinal \(\alpha\). For example, the figure represents \(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1}\), as explained in Kirby and Paris (1982).Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic" # Start from root node. # Going up one node from root node is expressed as adding an entry 0. # Going up one node is expressed as adding an entry of the value 1 larger than the previous entry. # Going down \(n\) nodes and going up one node for adjacent segment is expressed as adding an entry of the value \(n-1\) smaller than the previous entry. # Thus, the value of each entry expresses the height of the node from the root node - 1. # In the figure, first going up the highest \(\omega^{\omega^\omega}\) segment is expressed as (0,1,2,3). Then going down 3 nodes and going to the adjcent segment, entries (1,2,2,2) is added. After that, the segment (0,1,2,2,1) is added. Thus, the hydra tree is expressed as a sequence of (0,1,2,3,1,2,2,2,0,1,2,2,1). # We express this correspondence as \(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1} = (0,1,2,3,1,2,2,2,0,1,2,2,1)\). Here are examples. \begin{eqnarray*} 1 &=& (0) \\ 2 &=& (0,0) \\ 3 &=& (0,0,0) \\ \omega &=& (0,1) \\ \omega+2 &=& (0,1,0,0) \\ \omega \cdot 2 &=& (0,1,0,1) \\ \omega^2 &=& (0,1,1) \\ \omega^2+\omega &=& (0,1,1,0,1) \\ \omega^3 &=& (0,1,1,1) \\ \omega^\omega &=& (0,1,2) \\ \omega^{\omega^\omega} &=& (0,1,2,3) \\ \omega^{\omega^{\omega^\omega}} &=& (0,1,2,3,4) \\ \omega^{\omega^{(\omega^\omega+1)}} &=& (0,1,2,3,4,2) \\ \omega^{\omega^{\omega^{\omega^\omega}}} &=& (0,1,2,3,4,5) \\ \end{eqnarray*} Reading codes dim A(Infinity):B=9 A is for linear array and B is for the value. for C=0 to 9 This C loop repeats the \(B = f_{\epsilon_0}(B)\) calculation 10 times, therefore calculating \(f_{\epsilon_0+1}(10)\). for D=0 to B A(D)=D next It sets ordinal \(\omega\)^^\(B=(0,1,2,3,...,B)\). for E=B to 0 step -1 This loop is a little tricky because the value of E changes inside the loop. E represents the position of the last entry of the sequence, and therefore it starts from B. The remaining will be explained later. B=B*B At each step of cutting hydra head, B value is squared. If it is \(B=B+1\) it matches the Hardy hierarchy. As it uses \(B=B^2\), it is slightly larger than Hardy hierarchy. for F=0 to E if A(E-F) It calculates G, the length of the sequence where the hydra tree is copied. For example, for (0,1,2,3), G=1, meaning that after (3) is cut, (2) is copied. For (0,1,2,3,0), G=0, meaning that the hydra head is not copied. For (0,1,2,3,1), G=4, meaning that after (1) is cut, (0,1,2,3) is copied. for H=1 to B*G A(E)=A(E-G):E=E+1 next When G=0, this loop is not calculated, meaning that the hydra head is not cut off. In this case, at the start of the next loop, E is decreased by one, meaning that the rightmost node was cut off. Cut one hydra head and make B copies of hydra head expressed with the length G sequence. A(E)=A(E-G) is the operation of copying. It starts from A(E), meaning that the rightmost head was cut off. After copying, E=E+1 is calculated, and therefore the E is 1 larger than the position of the rightmost sequence. At the start of the next loop, E is decreased by one (STEP -1), and therefore it is cancelled. next next End of loops. print B Output the result. At first, A(0) to A(9) are set as \(A(n)=n\). This sequence is expressed as (0,1,2,3,4,5,6,7,8,9), and parameter E is set as E=9, where E represents the position at the end of the sequence. Example calculation Example calculation for this simplified code was shown by the author of the program.Example calculation posted at 2ch.net dim A(Infinity):B=2 for D=0 to B A(D)=D next for E=B to 0 step -1 for F=0 to E if A(E-F) The array is first initialized to \((0,1,2) = \omega\). At the loop of F, G=1. At the loop of H, E=4 and the array becomes \((0,1,1,1) = \omega^3\). After that, it goes to the second loop of E and E is decreased to 3 by STEP -1. Therefore, it matches the rightmost positio of the sequence (0,1,1,1). In this second loop of E, the array changes to \((0,1,1,0,1,1,0,1,1) = \omega^2 \cdot 3\). After this, the ordinal will decrease as *\((0,1,1,0,1,1,0,1,0,1,0,1) = \omega^2 \cdot 2 + \omega \cdot 3\) 0,1,1,0,1,1,0,1,0,1,0,0,0 ω^2*2+ω*2+34,14,12 この地点でGが0になる時が来ます。 0,1,1,0,1,1,0,1,0,1,0,0 ω^2*2+ω*2+25,14,11 0,1,1,0,1,1,0,1,0,1,0 ω^2*2+ω*2+16,14,10 0,1,1,0,1,1,0,1,0,1 ω^2*2+ω*27,14,9 この先、ωが１つ減るごとに、ループされた回数が+4、E=E+1が処理された回数が+2、 Eの値が-2されるので、省略していきます。 138 ：１３２人目の素数さん：2014/08/16(土) 21:09:49.81 0,1,1,0,1,1,0,1 ω^2*2+ω11,16,7 0,1,1,0,1,1 ω^2*215,18,5 0,1,1,0,1,0,1,0,1 ω^2+ω*316,22,8 0,1,1,0,1,0,1 ω^2+ω*220,24,6 0,1,1,0,1 ω^2+ω24,26,4 0,1,1 ω^228,28,2 0,1,0,1,0,1 ω*328,32,5 0,1,0,1 ω*232,32,3 0,1 ω36,34,1 ここでEの値ががループEの処理が始まる前のBよりも 1小さくなります。 139 ：１３２人目の素数さん：2014/08/16(土) 21:11:14.38 0,0,0 337,36,2 ここでA(0)～A(E)=0となります。 0,0 238,36,1 0 139,36,0 なお、0,1,2の列の最後に0が付くと、ω^ω+1 1が付くと、ω^(ω+1) 2が付くと、ω^(ω*ω) 3が付くと、ω^(ω^ω) 3,4が付くと、ω^(ω^(ω^ω)) というふうになります。 とりあえず説明は以上です。 Sources